home *** CD-ROM | disk | FTP | other *** search
/ The Atari Compendium / The Atari Compendium (Toad Computers) (1994).iso / files / umich / falcon / programm.ing / nt_dsp1.lzh / NT_DSP1.MSA / FFT / FFTR2EN.ASM < prev    next >
Assembly Source File  |  1990-01-17  |  10KB  |  239 lines
  1. ;
  2. ; This program originally available on the Motorola DSP bulletin board.
  3. ; It is provided under a DISCLAMER OF WARRANTY available from
  4. ; Motorola DSP Operation, 6501 Wm. Cannon Drive W., Austin, Tx., 78735.
  5. ; 
  6. ; 1024-Point, 3.23 ms Non-In-Place FFT, with normally ordered input and output
  7. ; 
  8. ; Last Update 18-Aug-88   Version 1.0
  9. ;
  10. ; Updated to use faster FFT method by overlapping the butterfly
  11. ;
  12. fftr2en   macro     data,coef,odata
  13. fftr2en   ident     1,0
  14. ;
  15. ; 1024 Point Complex Fast Fourier Transform Routine
  16. ;
  17. ; This routine performs a 1024 point complex FFT on external data
  18. ; using the Radix 2, Decimation in Time, Cooley-Tukey FFT algorithm.
  19. ;
  20. ;    Complex input and output data
  21. ;        Real data in X memory
  22. ;        Imaginary data in Y memory
  23. ;    Normally ordered input data
  24. ;    Normally ordered output data
  25. ;    Coefficient lookup table
  26. ;        -Cosine values in X memory
  27. ;        -Sine values in Y memory
  28. ;
  29. ; Macro Call - fftr2en  data,coef,odata
  30. ;
  31. ;    data       start of external data buffer
  32. ;    odata      start of external output data buffer
  33. ;    coef       start of sine/cosine table
  34. ;
  35. ; Radix 2, Decimation In Time Cooley-Tukey FFT algorithm
  36. ;             ___________
  37. ;            |           | 
  38. ; ar,ai ---->|  Radix 2  |----> ar',ai'
  39. ; br,bi ---->| Butterfly |----> br',bi'
  40. ;            |___________|
  41. ;                  ^
  42. ;                  |
  43. ;                wr,wi
  44. ;
  45. ;    ar' = ar + wr*br - wi*bi
  46. ;    ai' = ai + wi*br + wr*bi
  47. ;    br' = ar - wr*br + wi*bi = 2*ar - ar'
  48. ;    bi' = ai - wi*br - wr*bi = 2*ai - ai'
  49. ;
  50. ; Address pointers are organized as follows:
  51. ;
  52. ;    r0 = ar,ai input pointer    n0 = group offset          m0 = modulo (points)
  53. ;    r1 = br,bi input pointer    n1 = group offset          m1 = modulo (points)
  54. ;    r2 = ext. data base address n2 = groups per pass       m2 = 256 point fft counter
  55. ;    r3 = coef. offset each pass   n3 = coefficient base address m3 = linear
  56. ;    r4 = ar',ai' output pointer   n4 = group offset             m4 = modulo (points)
  57. ;    r5 = br',bi' output pointer   n5 = group offset             m5 = modulo (points)
  58. ;    r6 = wr,wi input pointer      n6 = coef. offset             m6 = bit reversed
  59. ;    r7 = not used (*)             n7 = output pointer storage   m7 = not used (*)
  60. ;
  61. ;    * - r7 and m7 are typically reserved for a user stack pointer.
  62. ;
  63. ; Alters Data ALU Registers
  64. ;    x1   x0   y1   y0
  65. ;    a2   a1   a0   a
  66. ;    b2   b1   b0   b
  67. ;
  68. ; Alters Address Registers
  69. ;    r0   n0   m0
  70. ;    r1   n1   m1
  71. ;    r2   n2   m2
  72. ;    r3   n3   m3
  73. ;    r4   n4   m4
  74. ;    r5   n5   m5
  75. ;    r6   n6   m6
  76. ;         n7
  77. ; Alters Program Control Registers
  78. ;    pc   sr
  79. ;
  80. ; Uses 8 locations on System Stack                                           
  81. ;
  82. ;
  83. _points   equ  1024      ;number of FFT points
  84. _intdata  equ  0         ;address of internal data workspace
  85.      move #data,r2       ;initialize input pointers
  86.      move r2,r0
  87.      move #_points/4,n0  ;initialize butterflies per group
  88.      move n0,n4          ;initialize pointer offsets
  89.      move n0,n6          ;initialize coefficient offset
  90.      move #coef,n3       ;initialize coefficient base address
  91.      move #_points-1,m0  ;initialize address modifiers
  92.      move m0,m1          ;for modulo(points) addressing
  93.      move m0,m4
  94.      move m0,m5
  95.      move #-1,m3         ;linear addressing for coefficient base offset
  96.      move #0,m2          ;initialize 256 point fft counter
  97.      move m2,m6          ;initialize coefficient address modifier
  98.                          ;for reverse carry (bit reversed) addressing
  99. ;                           
  100. ; Do first and second Radix 2 FFT passes as four-point butterflies
  101. ;
  102.      move           x:(r0)+n0,x0                  ;initialize butterfly
  103.      tfr  x0,a      x:(r0)+n0,y1                  ;
  104.  
  105.      do   n0,_twopass                             
  106.      tfr  y1,b      x:(r0)+n0,y0
  107.      add  y0,a      x:(r0),x1                     ;ar+cr
  108.      add  x1,b      r0,r4                         ;br+dr
  109.      add  a,b       (r0)+n0                       ;ar'=(ar+cr)+(br+dr)
  110.      subl b,a       b,x:(r0)+n0                   ;br'=(ar+cr)-(br+dr)
  111.      tfr  x0,a      a,x0           y:(r0),b
  112.      sub  y0,a                     y:(r4)+n4,y0   ;ar-cr
  113.      sub  y0,b      x0,x:(r0)                     ;bi-di
  114.      add  a,b                      y:(r0)+n0,x0   ;cr'=(ar-cr)+(bi-di)
  115.      subl b,a       b,x:(r0)                      ;dr'=(ar-cr)-(bi-di)
  116.      tfr  x0,a      a,x0           y:(r4),b
  117.      add  y0,a                     y:(r0)+n0,y0   ;bi+di
  118.      add  y0,b      x0,x:(r0)+n0                  ;ai+ci
  119.      add  b,a                      y:(r0)+,x0     ;ai'=(ai+ci)+(bi+di)
  120.      subl a,b                      a,y:(r4)+n4    ;bi'=(ai+ci)-(bi+di)
  121.      tfr  x0,a                     b,y:(r4)+n4
  122.      sub  y0,a      x1,b                          ;ai-ci
  123.      sub  y1,b      x:(r0)+n0,x0                  ;dr-br
  124.      add  a,b       x:(r0)+n0,y1                  ;ci'=(ai-ci)+(dr-br)
  125.      subl b,a                      b,y:(r4)+n4    ;di'=(ai-ci)-(dr-br)
  126.      tfr  x0,a                     a,y:(r4)+
  127. _twopass
  128. ;                                                                   
  129. ; Do remaining 8 FFT passes as four 256 point Radix 2 FFT's using internal data
  130. ; and external coefficients.
  131. ;
  132. ; Each 256 point Radix 2 FFT consists of 8 passes.  The first pass uses external
  133. ; input data and internal output data to move the data on-chip.  Intermediate
  134. ; passes use internal input data and internal output data to keep the data
  135. ; on-chip.  The last pass uses internal input data and external output data
  136. ; to move the data off-chip.
  137. ;
  138.      move #odata,r4      ;load output data address
  139.      do   #4,_end_fft    ;do 256 point fft four times
  140.      move r4,ssh         ;push output data address onto stack
  141.      move r2,r0          ;get external data input address for first pass
  142.      move m2,r3          ;update coefficient offset
  143.      move #256/2,n1      ;initialize butterflies per group
  144.      move #1,n2          ;initialize groups per pass
  145.  
  146.      do   #7,_end_pass   ;do first 7 passes out of 8
  147.      move #_intdata,r4   ;initialize A output pointer
  148.  
  149.      move n1,r5
  150.      move n1,n0          ;initialize pointer offsets
  151.      lua  (r5)-,n7
  152.  
  153.      move n1,n4
  154.      move n1,r6
  155.      lua  (r0)+n0,r1     ;initialize B input pointer
  156.      lua  (r4)+n4,r5     ;initialize B output pointer
  157.  
  158.      lua  (r6)+,n4
  159.      move n4,n5
  160.      lua  (r3)+n3,r6     ;initialize W input pointer
  161.      move n4,n0
  162. ;
  163. ;    initialize butterfly
  164.      move           x:(r1),x1      y:(r6),y0      ;lookup -sine value
  165.      move                          y:(r0),b
  166.      mac  x1,y0,b   x:(r6)+n6,x0   y:(r1)+,y1
  167.      macr -x0,y1,b                 y:(r0),a       ;
  168.                 
  169.      do   n2,_end_grp
  170.                                                  
  171.      do   n7,_end_bfy
  172.      subl b,a       x:(r0),b       b,y:(r4)
  173.      mac  -x1,x0,b  x:(r0)+,a      a,y:(r5)
  174.      macr -y1,y0,b  x:(r1),x1
  175.      subl b,a       b,x:(r4)+      y:(r0),b
  176.      mac  x1,y0,b                  y:(r1)+,y1     ;Radix 2 DIT butterfly kernel
  177.      macr -x0,y1,b  a,x:(r5)+      y:(r0),a       ;with constant twiddle factor
  178. _end_bfy             
  179.      move (r1)+n1
  180.      subl b,a       x:(r0),b       b,y:(r4)
  181.      mac  -x1,x0,b  x:(r0)+n0,a    a,y:(r5)
  182.      macr -y1,y0,b  x:(r1),x1      y:(r6),y0      ;lookup -sine value
  183.      subl b,a       b,x:(r4)+n4    y:(r0),b
  184.      mac  x1,y0,b   x:(r6)+n6,x0   y:(r1)+,y1
  185.      macr -x0,y1,b  a,x:(r5)+n5    y:(r0),a       ;
  186.  
  187. _end_grp            
  188.      move n1,b1
  189.      lsr  b    n2,a1               ;divide butterflies per group by two
  190.      lsl  a    b1,n1               ;multiply groups per pass by two
  191.      move      r3,b1     
  192.      lsr  b    a1,n2               ;divide coefficient offset by two
  193.      move      b1,r3
  194.      move      #_intdata,r0        ;intermediate passes use internal input data
  195. _end_pass
  196. ;        
  197. ; Do last FFT pass and move output data off-chip to external data memory.
  198. ;
  199.      move n7,r1
  200.      move ssh,r4
  201.      move (r1)+
  202.  
  203.      move r1,n0
  204.      move r1,n1